﻿// 0811train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;

/*
 某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，
 为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。
约束：
1. 一个团只能上一辆车，并且代表团人数（代表团数量小于30，每个代表团人数小于30）小于汽车容量（汽车容量小于100）
2. 需要将车辆坐满

输入描述
第一行代表团人数，英文逗号隔开，代表团数量小于30，每个代表团人数小于30
第二行汽车载客量，汽车容量小于100

输出描述
坐满汽车的方案数量
如果无解输出0

示例1
输入
5,4,2,3,2,4,9
10
输出
4
 */

void solve01(vector<int>&item_vec, int target)
{
	//前i个数中，凑出w的方案数
	//curr_w
	//dp[i][w]=dp[i-1][w]
	//dp[i][w]=dp[i-1][w]+dp[i-1][w-curr_w]

	//边界情况
	//dp[i][0]=1 dp[0][i]=0;
	int dp_size = item_vec.size() + 1;
	int target_size = target + 1;
	vector<int>target_vec(target_size, 0);
	vector<vector<int>>dynamic_grid(dp_size, target_vec);

	for (int i=0; i<dp_size; i++)
	{
		dynamic_grid[i][0] = 1;
	}

	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<target_size; w++)
		{
			int curr_w = item_vec[i-1];
			if (w<curr_w)
			{
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				int inherit = dynamic_grid[i - 1][w];
				dynamic_grid[i][w] = inherit + dynamic_grid[i - 1][w - curr_w];
			}
		}
	}

	cout << dynamic_grid[dp_size-1][target];
	//solve01
}


/*
 从n个数中选若干（至少1）个数求和，求所有方案中第k小的和（和相同但取法不同的视为不同方案）。
对于所有数据，1 <= k < 2^n， n个正整数每个都不超过10^9。
输入描述
第一行输入2个正整数n, k。
第二行输入这n个正整数。

输出描述
输出第k小的和。

示例1
输入
5 12
1 2 3 5 8
输出
8
 */

void solve02(vector<int>&item_vec, int k)
{
	//1先求出total_sum
	//2 int dp_size = total_sum+1
	//3 边界条件 dp[0]=1 凑齐0始终有一种方案
	int total_sum = 0;
	for (auto&num:item_vec)
	{
		total_sum += num;
	}
	vector<int>dynamic_vec(total_sum+1);

	for (auto&num:item_vec)
	{
		for (int prev_sum=total_sum-num; prev_sum>=0; prev_sum--)
		{
			int path_num = dynamic_vec[prev_sum];
			int curr_sum = prev_sum + num;
			dynamic_vec[curr_sum] += path_num;
		}

	}



	//cout << result_vec[k-1];

	//solve02------
}


/*
 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
 */
int GetStartPos(vector<int>& nums, int target)
{
	int vec_size = nums.size();
	int left = 0;
	int right = vec_size - 1;

	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == target)
		{
			if (mid == 0 || nums[mid - 1] < target)
			{
				return mid;
			}
			right = mid - 1;
		}
		else if (nums[mid] > target)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}

	}
	return -1;
	//GetStartPos
}

int GetEndPos(vector<int>& nums, int target)
{
	int vec_size = nums.size();
	int left = 0;
	int right = vec_size - 1;

	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == target)
		{
			if (mid == vec_size-1 || nums[mid + 1] > target)
			{
				return mid;
			}
			left = mid + 1;
		}
		else if (nums[mid] > target)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}

	}
	return -1;
	//GetEndPos
}


vector<int> searchRange(vector<int>& nums, int target) {

	int start_pos = GetStartPos(nums, target);
	int end_pos = GetEndPos(nums, target);

	return { start_pos,end_pos };
	//searchRange
}

/*
 给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如  sqrt
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数
 */

bool isPerfectSquare(int num) {
	if (num == 1)
		return true;
	for (int i = 0; i <= num / 2; i++) {
		long long_num = num;
		if ((long)i * i == long_num) {
			return true;
		}
	}
	return false;
}

bool isPerfectSquare01(int num)
{
	int left = 0;
	int right = num;

	while (left<=right)
	{
		int mid = left + (right - left) / 2;
		long double_mid = (long)mid * mid;

		if (double_mid< num)
		{
			left = mid + 1;
		}
		else if (double_mid> num)
		{
			right = mid - 1;
		}
		else if (double_mid== num)
		{
			return true;
		}

	}
	return false;

	//isPerfectSquare01
}


int main()
{
	{
		cout << isPerfectSquare(16);
		return 0;
	}
	{
		//nums = [5,7,7,8,8,10], target = 8
		vector<int>nums = { 5,7,7,8,8,10 };
		int target = 8;
		vector<int>result = searchRange(nums, target);

		for (auto&num:result)
		{
			cout << num << ' ';
		}

		return 0;
	}

	{
		//1 2 3 5 8
		vector<int>item_vec = { 1,2,3,5,8 };
		int k = 12;
		solve02(item_vec, k);

		return 0;
	}

	vector<int>item_vec;
	string input;
	getline(cin, input);
	stringstream oh_sstream(input);
	string token;
	while (getline(oh_sstream, token, ','))
	{
		item_vec.push_back(stoi(token));
	}

	int target;
	cin >> target;

	//for (auto&num:item_vec)
	//{
	//	cout << num << ' ';
	//}
	//vector<int>item_vec = { 5,4,2,3,2,4,9 };
	//int target = 10;
	solve01(item_vec, target);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
